package com.mdnote.jianzhi_offer.linked_list;

import com.mdnote.practice.binary_tree.LeetCode226;
import org.junit.Assert;
import org.junit.Test;
import sun.reflect.generics.tree.Tree;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/11/10 0:58
 * @Email rhythm_2019@163.com
 * @Description 剑指Offer23  链表中环的入口节点
 */
public class Offer23 {


    public ListNode entryNodeOfList(ListNode head) {

        // 找到环中任意元素
        ListNode meetingNode = findMeetingNode(head);
        if (meetingNode == null) {
            return null;
        }

        // 计算环元素个数
        int count = getNodeCount(meetingNode);

        ListNode fast = head, slow = head;
        // 先让fast走count
        for (int i = 0; i < count; i++) {
            fast = fast.next;
        }
        // slow 和 fast 同时移动直至相遇
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }

        return slow;
    }

    private int getNodeCount(ListNode meetingNode) {
        int count = 1;
        ListNode tmp = meetingNode.next;
        while (tmp != meetingNode) {
            tmp = tmp.next;
            count++;
        }
        return count;
    }

    private ListNode findMeetingNode(ListNode head) {
        ListNode fast = head, slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (slow == fast) {
                return slow;
            }
        }
        return null;
    }

    public static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }


    @Test
    public void test_01() {
        Offer23 offer23 = new Offer23();
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        ListNode meetingNode = new ListNode(4);
        head.next.next.next = meetingNode;
        head.next.next.next.next = new ListNode(5);
        head.next.next.next.next.next = new ListNode(6);
        head.next.next.next.next.next.next = new ListNode(7);
        head.next.next.next.next.next.next.next = meetingNode;
        ListNode enter = offer23.entryNodeOfList(head);

        Assert.assertEquals(4, enter.val);

    }
}
